package sort;



/**
 * @BelongsProject: leetcode
 * @BelongsPackage: sort
 * @author: 肖
 * @date: 2022/1/25 19:29
 * @Description: 基数排序
 * @since JDK 11
 */

public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }

    private static int maxBits(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    //    digit 最大位
    public static void radixSort(int[] arr, int l, int r, int digit) {
        //    基底
        final int radix = 10;
        int i = 0, j = 0;
        int[] bucket = new int[r - l + 1];
//        有多少位就进出几次
        for (int d=1;d<=digit;d++){
//            保存前缀和
            int[] count = new int[radix];
            for(i = l ;i<=r;i++){
                j=getDigit(arr[i],d);
                count[j]++;
            }
            for ( i=1;i<radix;i++){
                count[i] = count[i]+count[i-1];
            }
            for(i = r; i>=l;i--){
                j=getDigit(arr[i],d);
                bucket[count[j]-1] = arr[i];
                count[j]--;
            }
            for ( i =l,j=0;i<=r;i++,j++){
                arr[i]= bucket[j];
            }
        }
    }

    private static int getDigit(int x, int d) {
        return ((x/((int)Math.pow(10,d-1)))%10);
    }

}
